00100	                         STANFORD UNIVERSITY		       
00200	                    COMPUTER  SCIENCE  DEPARTMENT
00300	                            SPRING,   1974
00400	
00500	                   MODELS  OF  THOUGHT  PROCESSES
00600	                     (artificial intelligence)
00700				     CS  224
00800		              T Th 1:15-2:30, Room 300
00900	
01000	            Handout #2       April 9, 1974
01100	
01200		Homework #2 	   Due:  April 16, 1974
01300	
01400	You are to do the following two problems in Nilsson's book:
01500		3.1  (propose as many h functions as you can, but only carry
01600	               out the the graphing process for one or two h functions)
01700		4.6
01800	
01900	In addition, the following optional problem is interesting, and is
02000	supplied with a hint to get you started.  If you need more help, or
02100	wish to check your solution yourself, a detailed discussion of this
02200	problem is provided in Ernst, G. (1969) "Sufficient Conditions for
02300	the Success of GPS", in JACM, vol. 16, no. 4 (Oct, 1969) pp 517-533.
02400	
02500	Optional Problem: Consider the Tower of Hanoi problem, let us say 
02600	with four disks and, as usual, three pegs. Try to view this as a
02700	difference reduction problem.  Your task is to find a set of
02800	differences, an associated operator with each difference, and a
02900	linear ordering of the differences,  which guarantees that you 
03000	will go directly to the solution. We assume here that you are
03100	doing a GPS-like search: find the differences between current
03200	and desired states, pick the most important difference, find its
03300	associated operator, satisfy its preconditions, and then apply it.
03400	
03500	Hint: to help you get started on the optional problem, here is one
03600	way to represent an operator:
03700	There is one operator for each disk d and pair of pegs p1 and p2
03800	(thus there are 4x3x3 = 36 operators). The operator moves disk d
03900	from p1 to p2.  What are the preconditions? Recall that at each
04000	instant, no disk can support a bigger one than itself.
04100	So you must now think up a set of differences and, for each,
04200	associate one of these operators. Think about this: there may not
04300	necessarily be the same number of differences as there are operators.
04400	In fact, one may devise a set of four simple differences which
04500	suffice. Be careful about arranging these in the proper order
04600	of importance. Is there a connection between the most important
04700	diference and what move you actually make first? Between the
04800	least important difference and the move you make first?  Explain.
04900	
05000	If we eliminate the requirement  of guaranteeing direct progress to 
05100	the goal, what feature(s) of the possible solutions changes? For
05200	eaxample, need we have exactly one operator associated with each
05300	difference?  If not, is there ANY structure noticable in the table
05400	of differences vs operators?
05500	Good luck!!